#include <utility>
#include <vector>
#include <string>

namespace closedHashTable {
	enum class Status {
		EMPTY,
		EXIST,
		DELETE
	};

	template<class T>
	struct HashData {
		T _data;
		Status _status;

		HashData()
			: _data(T())
			, _status(Status::EMPTY)
		{}
	};

	template<class K, class T, class KOFD>
	class HashTable {
	private:
		typedef HashData<T> Data;
		typedef HashTable<K, T, KOFD> Self;
	private:
		std::vector<Data> _table;
		size_t _size; //记录哈希表中已经存储有效数据的个数

	public:
		HashTable()
			: _size(0)
		{
			_table.resize(10); //为哈希表开辟最初的容量
		}

		bool insert(const T& data)
		{
			if (find(data))
			{
				return false;
			}

			//计算负载因子，判断是否需要扩容(闭散列的负载因子一般不大于0.7)
			//负载因子 = 有效数据 / 哈希表容量

			if (_size * 10 / _table.size() > 7) //_size * 1.0 / _table.size() > 0.7
			{
				Self temp;
				temp._table.resize(_table.size() * 2); //扩容两倍

				for (auto& d : _table)
				{
					if (d._status == Status::EXIST)
					{
						temp.insert(d._data); //通过调用自身来完成哈希表中数据的复制
					}
				}

				//通过交换，将扩容前的哈希表变成temp中的内容(局部变量)销毁
				_table.swap(temp._table);
			}

			KOFD getKeyOf;
			size_t index = getKeyOf(data) % _table.size();
			//线性探测
			//while (_table[index]._status == Status::EXIST)
			//{
			//	++index;
			//	index %= _table.size();
			//}

			//二次探测，能够避免哈希冲突堆在一块
			size_t i = 1;
			while (_table[index]._status == Status::EXIST)
			{
				index = index + i * i;
				++i;
			}

			_table[index]._data = data;
			_table[index]._status = Status::EXIST;
			++_size;

			return true;
		}

		bool erase(const T& data)
		{
			Data* ret = find(data);
			if (ret) //ret != nullptr
			{
				//采取消极的删除方式，就像inode一样
				ret->_status = Status::DELETE;
				--_size;
				return true;
			}
			else
			{
				return false;
			}
		}

		Data* find(const T& data)
		{
			KOFD getKeyOf;
			size_t index = getKeyOf(data) % _table.size(); //除留余数法是除上哈希表的容量而不是有效数据的个数，哈希表的容量为size()的大小
			while (_table[index]._status != Status::EMPTY)
			{
				if (_table[index]._status == Status::EXIST && getKeyOf(data) == getKeyOf(_table[index]._data))
				{
					return &_table[index];
				}

				++index;
				if (index == _table.size() - 1) //或者不需要判断写成index %= _table.size();
				{
					index = 0;
				}
			}

			//因为哈希表不可能存在满的情况，所以当找不到的时候一定会退出循环
			return nullptr;
		}
	};
}

namespace hash_bucket {

	//仿函数，将unordered_set和unordered_map中的key值转化为size_t(usinged int)类型，从而使key可以进行模运算。（主要是为了处理当key为string类型的情况）
	//tips: C/C++中的%运算要求操作符左右两边都为整形，而Java中没有这个要求，其可以为浮点数。
	template<class K>
	struct HashKeyConvertToUI/*usigned int*/ {
		const size_t operator() (const K& key) const
		{
			return (size_t)key;
		}
	};

	template<> //模板特化，专门处理当K为string类型的情况
	struct HashKeyConvertToUI<std::string> {
		const size_t operator() (const std::string str) const
		{
			size_t ret = 0;
			for (const auto& ch : str)
			{
				//为了避免如果只是单纯的将字符串每个字符的ASCII码值加起来（这种情况会导致哈希冲突较多，如aadd和abcd的ASCII总值是一样的）
				//所以使用字符串哈希算法，即*=131（31, 131, 1313, 13131......）这样可以减少哈希冲突
				//Java中的HashMap也是运用了这种方法减少哈希冲突，不过它在实现时是*=31。
				ret *= 131;
				ret += ch;
			}

			return ret;
		}
	};

	//除了可以对key为string的情况进行特化外，还可以对key为结构体等的情况进行特化，这时候要将结构体中的数据作为标识，如果结构体中有字符串，就以字符串为标识
	//template<> struct HashKeyConvertToUI<结构体名>


	template<class T>
	struct HashBucketNode {
		T _data;
		HashBucketNode<T>* _next;//指向哈希桶中的下一个节点。如果一个哈希桶的长度过长的话，就将链表改为红黑树(Java中链表的长度>8时，就改为红黑树)

		//如果想要保证迭代器遍历时是按照插入顺序来遍历的话(STL中就是这样的)，可以再添加两个指针
		/*
			HashBucketNode<T>* _insertNext;//指向按照插入顺序的下一个节点，用于插入和遍历
			HashBucketNode<T>* _insertPrev;//指向按照插入顺序的上一个节点，用于删除
		*/

		HashBucketNode(const T& data)
			: _data(data)
			, _next(nullptr)
		{}
	};

	//前置声明
	//因为C++在找东西时是在使用的地方向上找，且在__HashTableIterator中用到了在其后面的HashTable，所以要在__HashTableIterator的前面先声明一下这个类。
	//不能将HashTable放在__HashTableIterator的前面来解决问题，因为HashTable中也用到了__HashTableIterator，两者相互依赖；
	//就算调换了位置，也要在HashTable的前面声明一下__HashTableIterator。
	template<class K, class T, class Hash, class KOFT>
	class HashTable;

	template<class K, class T, class Hash, class KOFT>
	class __HashTableIterator {
	private:
		typedef HashBucketNode<T> Node;
		typedef __HashTableIterator<K, T, Hash, KOFT> Self;
		typedef HashTable<K, T, Hash, KOFT> HashTable;
		typedef T* Ptr;
		typedef T& Ref;

	private:
		Node* _node; //指向哈希桶中的节点
		HashTable* _ht; //指向哈希桶所在的哈希表，方便遍历完一个桶后找到下一个桶

	public:
		__HashTableIterator(const Node*& node, const HashTable*& ht)
			: _node(node)
			, _ht(ht)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		bool operator==(const Self& s) const
		{
			return _node == s._node;
		}

		bool operator!=(const Self& s) const
		{
			return _node != s._node;
		}

		Self& operator++()
		{
			//一个桶没有走完，找这个桶的下一个节点
			if (_node->_next)
			{
				_node = _node->_next;
			}

			//一个桶走完了，找下一个桶
			KOFT getKeyOf;
			size_t i = Hash()(getKeyOf(_node->_data)) % _ht->_table.size();
			++i;
			while (i < _ht->_table.size())
			{
				if (_ht->_table[i])
				{
					_node = _ht->_table[i];
					break;
				}

				++i;
			}

			//全部桶都走完了
			if (i == _ht->_table.size())
			{
				_node == nullptr;
			}

			return *this;
		}
	};

	template<class K, class T, class Hash, class KOFT>
	class HashTable {
	private:
		typedef HashBucketNode<T> Node;
		template<class K, class T, class Hash, class KOFT>
		friend class __HashTableIterator;

	private:
		std::vector<Node*> _table;
		size_t _num;

	public:
		typedef __HashTableIterator<K, T, Hash, KOFT> iterator;

	public:
		HashTable()
			: _num(0)
		{
			_table.resize(__stl_next_prime(0));
		}

		~HashTable()
		{
			for (auto& ptr : _table)
			{
				Node* cur = ptr;
				while (cur)
				{
					Node* next = cur->_next;

					delete cur;

					cur = next;
				}

				ptr = nullptr;
			}

			_num = 0;
		}

		std::pair<iterator, bool> insert(const T& data)
		{
			KOFT getKeyOf;
			iterator it = find(getKeyOf(data));
			if (it != end()) return std::make_pair<it, false>;

			//开散列(哈希桶)的负载因子为1时就需要扩容了
			if (_num == _table.size())
			{
				std::vector<Node*> newHashTable;
				newHashTable.resize(__stl_next_prime(_table.size()));

				for (auto& ptr : _table)
				{
					Node* cur = ptr;
					while (cur)
					{
						Node* next = cur->_next;

						//将在原哈希表上的节点直接移到新哈希表上
						size_t i = Hash()(getKeyOf(cur->_data)) % newHashTable.size();
						cur->_next = newHashTable[i];
						newHashTable[i] = cur;

						cur = next;
					}

					ptr = nullptr;
				}

				_table.swap(newHashTable);
			}

			size_t i = Hash()(getKeyOf(data)) % _table.size();
			Node* newNode = new Node(data);
			newNode->_next = _table[i];
			_table[i] = newNode;
			++_num;

			return std::make_pair(iterator(newNode, this), true);
		}

		bool erase(const K& key)
		{
			KOFT getKeyOf;
			size_t i = Hash()(key) % _table.size();

			Node* cur = _table[i];
			Node* prev = nullptr;

			while (cur)
			{
				if (getKeyOf(cur->_data) == key)
				{
					if (prev == nullptr) //头删
					{
						_table[i] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}

					delete cur;
					--_num;

					return true;
				}

				prev = cur;
				cur = cur->_next;
			}

			return false;
		}

		iterator find(const K& key)
		{
			KOFT getKeyOf;
			size_t i = Hash()(key) % _table.size();
			Node* cur = _table[i];
			while (cur)
			{
				if (getKeyOf(cur->_data) == key)
				{
					return iterator(cur, this);
				}

				cur = cur->_next;
			}

			return end();
		}

		iterator begin()
		{
			for (auto& ptr : _table)
			{
				if (ptr)
				{
					return iterator(ptr, this);
				}
			}

			return end();
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

	private:
		inline unsigned long __stl_next_prime(unsigned long n)
		{
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			for (int i = 0; i < __stl_num_primes; ++i)
			{
				if (__stl_prime_list[i] > n)
				{
					return __stl_prime_list[i];
				}
			}

			return __stl_prime_list[__stl_num_primes - 1];
		}
	};
}